package com.more.offer.algorithm.sort.sort_01;

/**
 * Date: 2020-03-15 23:14
 * Author: pinoc
 * Desc:
 */
public class MergeSort {
	public static void merge(int []a,int left,int mid,int right){
		//辅助数组
		int []tmp=new int[a.length];
		//p1、p2是检测指针，k是存放指针
		int p1=left,p2=mid+1,k=left;

		while(p1<=mid && p2<=right){
			if(a[p1]<=a[p2]) {
				tmp[k++]=a[p1++];
			}
			else {
				tmp[k++]=a[p2++];
			}
		}
		while(p1<=mid) {
			//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
			tmp[k++]=a[p1++];
		}
		while(p2<=right){
			//同上
			tmp[k++]=a[p2++];
		}

		//复制回原素组
		for (int i = left; i <=right; i++) {
			a[i]=tmp[i];
		}
	}

	public static void mergeSort(int[] a,int start,int end){
		if(start<end){
			int mid = (start+end) >> 1;
			mergeSort(a,start,mid);
			mergeSort(a,mid+1,end);
			merge(a,start,mid,end);
		}
	}

	public static void main(String[] args) {
		int [] a = {1,3,2,4,-1,-10,100,200,-50,-3};
		mergeSort(a,0,a.length-1);
		for(int i: a){
			System.out.print(i+" ");
		}
		System.out.println();
		if((a.length % 2) == 0) {
			int left = a[a.length/2 - 1];
			int right = a[a.length/2];
			double mid = (left + right) / 2.0;

			System.out.println(mid);
		}
	}
}
